package com.zengqingfa.algorithm.cz.chapter03;

import java.util.Iterator;

/**
 * @author zengqingfa
 * @className SequenceList
 * @description 顺序表
 * @create 2021/8/24 23:01
 */
public class SequenceList<T> implements Iterable {

    //存储元素的数组
    private T[] elements;
    //顺序表中元素的个数
    private int size;

    /**
     * 根据容量构建线性表
     *
     * @param capacity
     */
    public SequenceList(int capacity) {
        this.elements = (T[]) new Object[capacity];
        this.size = 0;
    }

    /**
     * 清空线性表
     */
    public void clear() {
        size = 0;
    }

    /**
     * 判断当前线性表是否为空
     *
     * @return
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 获取线性表的长度
     *
     * @return
     */
    public int length() {
        return size;
    }

    /**
     * 获取索引index处的元素
     *
     * @param index
     * @return
     */
    public T get(int index) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("索引非法");
        }
        return elements[index];
    }


    /**
     * 添加元素
     *
     * @param t
     */
    public void insert(T t) {
        if (size == elements.length) {
            resize(elements.length * 2);
        }
        elements[size++] = t;
    }

    /**
     * 扩容
     *
     * @param capacity
     */
    private void resize(int capacity) {
        T[] eles = elements;
        //创建新的数组
        elements = (T[]) new Object[capacity];
        //把旧数组拷贝到新数组
        for (int i = 0; i < size; i++) {
            elements[i] = eles[i];
        }
    }


    /**
     * 添加元素
     *
     * @param t
     */
    public void insert(T t, int index) {
        //大小与数组的长度相等，表示已满
        if (size == elements.length) {
            resize(size * 2);
        }
        //插入的位置小于0或者大于等于数组的长度非法
        if (index < 0 || index >= elements.length) {
            throw new IllegalArgumentException("插入位置不合法");
        }
        //从size处往后移动元素
        for (int i = size - 1; i >= index; i--) {
            elements[i + 1] = elements[i];
        }
        elements[index] = t;
        size++;
    }


    /**
     * 删除索引index处的元素
     *
     * @param index
     * @return
     */
    public T remove(int index) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("删除位置不合法");
        }
        T result = elements[index];
        for (int i = index; i < size; i++) {
            elements[i] = elements[i + 1];
        }
        size--;
        //如果当前元素已不足数组的四分之一，则缩容
        if (size > 0 && size < elements.length / 4) {
            resize(elements.length / 2);
        }
        return result;
    }


    /**
     * 查找第一个元素为t的索引
     *
     * @param t
     * @return
     */
    public int indexOf(T t) {
        if (t == null) {
            throw new RuntimeException("查找的元素不合法");
        }
        for (int i = 0; i < size; i++) {
            if (elements[i].equals(t)) {
                return i;
            }
        }
        return -1;
    }


    /**
     * 获取迭代器，实现可迭代的功能
     *
     * @return
     * @see java.util.Iterator
     */
    @Override
    public Iterator iterator() {
        return new LIterator();
    }

    /**
     * 迭代器
     */
    private class LIterator implements Iterator {

        private int cur;

        public LIterator() {
            this.cur = 0;
        }

        @Override
        public boolean hasNext() {
            return cur < size;
        }

        @Override
        public Object next() {
            return elements[cur++];
        }
    }
}